Euler đã chứng minh được rằng các biểu diễn phẳng khác nhau của một đồ thị đều chia mặt phẳng ra thành cùng một số miền qua định lý sau (thường được gọi là công thức Euler):

Chứng minh: Cho G là đồ thị phẳng liên thông có n đỉnh, m cạnh và r miền. Ta bỏ một số cạnh của G để được một cây khung của G. Mỗi lần ta bỏ một cạnh (m giảm 1) thì số miền của G cũng giảm 1 (r giảm 1), còn số đỉnh của G không thay đổi (n không đổi). Như vậy, giá trị của biểu thức n - m + r không thay đổi trong suốt quá trình ta bỏ bớt cạnh của G để được một cây. Cây này có n đỉnh, do đó có n - 1 cạnh và cây chỉ có một miền, vì vậy: n - m + r = n - (n -1) + 1 = 2.

Hệ thức n - m + r = 2 thường gọi là hệ thức Euler cho hình đa diện, vì được Euler chứng minh đầu tiên cho hình đa diện có n đỉnh, m cạnh và r mặt.

Một hệ quả đơn giản là:

Chứng minh: Trong đồ thị phẳng mỗi miền được bao bằng ít nhất 3 cạnh. Mặt khác, mỗi cạnh có thể nằm trên biên của tối đa hai miền. Gọi d là số miền, thì 3d ≤ 2p. Nếu trong đồ thị phẳng mà tất cả các đỉnh đều có bậc không nhỏ hơn 6 thì do mỗi đỉnh của đồ thị phải là đầu mút của ít nhất 6 cạnh mà mỗi cạnh lại có hai đầu mút nên ta có 6n ≤ 2p hay 3n ≤ p. Từ đó suy ra 3d+3n ≤ 2p+p hay d+n ≤ p, trái với hệ thức Euler d+n = p+2.